// Growth rate calculator.
// DFA is a trie-like deterministic finite automaton used to
// store the set of minimal forbidden words in a language.
// It is used in:
// 1) constructing the set of forbidden words (at this moment dfa
//    is essentially a trie and is filled with words one by one).
// 2) transforming the trie into a complete DFA using modified
//    Aho-Corasick algorithm.
// 3) calculating the growth rate of a language by finding the maximal
//    eigenvalue of adjacency matrix of a finite automaton. This step
//    is performed by efficient numerical method.

// Use case:
// 0. Create LexminTrie with fixed capacity and alphabet_size.
// 1. Fill the LexminTrie with forbidden words using methods:
//    add_lexmin_words() and accepts_word().
// 2. Create LexminDFA using built LexminTrie.
// 3. Calculate the growth rate of a given DFA.

// We focus our attention on symmetrical languages. In these languages
// if a word w is forbidden, then any word which can be obtained by renaming
// the letters is also forbidden. In LexminTrie and LexminDFA we store
// the lexmin representative for each class of forbidden words. When we
// "add" a word to the LexminDFA, we check that it is indeed lexmin.
// When we check if a prefix/suffix of a word is forbidden, we check if
// its lexmin equivalent is forbidden.

#ifndef GRATE_DFA_H
#define GRATE_DFA_H

#include <string>
#include "util/common.h"
#include "util/word.h"

namespace growth_rate {

struct SccPartition;

class DFAInterface {
 public:
  static const int UnknownNode = -2;
  static const int FakeSink = -1;
  static const int StartNode = 0;

  virtual ~DFAInterface() { }

  // True if size, alphabet size and transition tables are equal.
  bool equals(const DFAInterface& other) const;
  // Dump transitions table in a human-readable format.
  std::string dump_transitions() const;
  struct Edge {
    int from;
    int to;
  };
  // Dumps all edges that doesn't lead to fake sink or unknown node.
  // REQUIRES: input array must have sufficient size.
  void dump_valid_edges(Edge *edges) const;

  // Drop all nodes except for those lying in single scc. Renumerate
  // the nodes and shrink edges array accordingly.
  void leave_single_scc(const SccPartition *scc_partition);

  int get_next(int node, uint8_t letter) const {
    CHECK(0 <= node && (size_t)node < size_);
    CHECK_LT(letter, alphabet_size_);
    return edges_[node * alphabet_size_ + letter];
  }
  void set_next(int node, uint8_t letter, int next) {
    CHECK(0 <= node && (size_t)node < size_);
    CHECK_LT(letter, alphabet_size_);
    CHECK(next == FakeSink || (0 <= next && (size_t)next < size_));
    edges_[node * alphabet_size_ + letter] = next;
  }

  // Checks if there is an edge from node to itself.
  bool has_loop(size_t node) const {
    DCHECK_LT(node, size_);
    for (uint8_t letter = 0; letter < alphabet_size_; ++letter) {
      if (get_next(node, letter) == node)
        return true;
    }
    return false;
  }

  // Returns the number of edges in scc that doesn't lead to fake sink
  // or unknown node.
  size_t number_of_valid_edges() const {
    size_t result = 0;
    for (int node = StartNode; node < size_; node++) {
      for (uint8_t letter = 0; letter < alphabet_size_; letter++) {
        if (get_next(node, letter) >= StartNode)
          result++;
      }
    }
    return result;
  }

  size_t size() const { return size_; }
  uint8_t alphabet_size() const { return alphabet_size_; }
  size_t transition_table_size() const {
    return sizeof(edges_[0]) * size_ * alphabet_size_;
  }

 protected:
  DFAInterface(size_t start_size, uint8_t alphabet_size)
    : size_(start_size),
      alphabet_size_(alphabet_size),
      edges_(0) { }

  size_t size_;  // Number of nodes.
  const uint8_t alphabet_size_;
  int *edges_;  // Dynamically allocated storage for dfa edges
                // (buffer of size at least size_ * alphabet_size_).
                // Concrete subclasses of DFAInterface should be responsible
                // for initializing and deleting edges.

 private:
  virtual void shrink_size(size_t new_size) = 0;

  // Eigenvalue calculator may modify the internals of dfa and even
  // delete it.
  friend class EigenvalueCalculator;
};

class LexminTrie : public DFAInterface {
 public:
  LexminTrie(size_t capacity, uint8_t alphabet_size);
  ~LexminTrie() {
    FreeArray(&edges_);
  }

  // Returns true if the word was successfully added to the trie,
  // or false if the LexminDFA is full or if the word is already forbidden.
  bool add_lexmin_word(const Word &word);
  // Returns true if a current automaton accepts the lexmin equivalent of
  // a given word (i.e. reading it doesn't lead to a sink)
  // read in a given direction.
  bool accepts_word(const Word &word, Direction direction) const;

  size_t number_of_leaf_nodes() const { return leaf_nodes_; }
  // Transfers ownership of transition table (edges) to the caller.
  int *take_edges() {
    int *edges = edges_;
    edges_ = 0;
    return edges;
  }

 private:
  void shrink_size(size_t new_size) {
    CHECK_LE(new_size, size_);
    ReallocateArray(&edges_, new_size * alphabet_size_);
    size_ = new_size;
  }

  // Returns false if the automaton is full already.
  bool create_empty_vertex();

  const size_t capacity_;  // Maximal possible number of nodes.
  size_t leaf_nodes_;  // Number of leaf nodes.
};

// LexminDFA can viewed as a simple table of size [capacity] x [alphabet_size]
// dfa.get_next(i, j) is a number of node obtained by reading letter "j" at
// position "i" (where 0 <= i < size and 0 <= j < alphabet_size). It is:
//   LexminDFA::FakeSink, if this transition goes to a single (fake)
//                       unacceptable state;
//   LexminDFA::UnknownNode, if the transition is undefined;
//   non-negative number, if the transition is defined.
// Initial node is LexminDFA::StartNode (it has number 0).
class LexminDFA : public DFAInterface {
 public:
  explicit LexminDFA(LexminTrie *trie);
  ~LexminDFA() {
    FreeArray(&edges_);
  }

 private:
  void shrink_size(size_t new_size) {
    CHECK_LE(new_size, size_);
    ReallocateArray(&edges_, new_size * alphabet_size_);
    size_ = new_size;
  }
};

}  // namespace growth_rate

#endif  // GRATE_DFA_H
